/*
leetcode 383. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

 

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true
 

提示：

1 <= ransomNote.length, magazine.length <= 10^5
ransomNote 和 magazine 由小写英文字母组成
*/

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 创建一个大小为 26 的数组来记录每个字母的频次（假设字符都是小写字母）
        vector<int> magazineCount(26, 0);
        
        // 填充 magazineCount，统计 magazine 中每个字母的出现次数
        for (char c : magazine) {
            magazineCount[c - 'a']++;
        }
        
        // 遍历 ransomNote，检查 magazine 中是否有足够的字母
        for (char c : ransomNote) {
            int index = c - 'a';
            if (magazineCount[index] > 0) {
                magazineCount[index]--;  // 使用一个字符
            } else {
                return false;  // 如果没有足够的字符，返回 false
            }
        }
        
        return true;  // 如果所有字符都满足，返回 true
    }
};

int main() {
    Solution solution;

    // 测试用例
    string ransomNote = "aa";
    string magazine = "aab";
    
    // 输出结果
    if (solution.canConstruct(ransomNote, magazine)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

/*
假设我们有以下输入：

ransomNote = "aa"
magazine = "aab"
我们使用一个数组 magazineCount 来记录 magazine 中每个字母的出现次数，使用一个循环来遍历 ransomNote 的每个字母，检查 magazineCount 中是否有足够的字母。

步骤 1：初始化 magazineCount 数组
首先，我们需要一个大小为 26 的数组来存储 magazine 中每个字母的频次（因为字母表中只有 26 个字母，且假设字符都是小写字母）。
vector<int> magazineCount(26, 0);
magazineCount 数组初始化为：
magazineCount = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

步骤 2：填充 magazineCount 数组
然后，我们遍历 magazine 字符串，统计每个字母出现的次数，并将计数存入 magazineCount 数组。
magazine = "aab"

遍历 magazine 中的字符：
对于字符 'a'，它对应的索引是 0，所以 magazineCount[0] 增加 1。
对于字符 'a'，它对应的索引是 0，所以 magazineCount[0] 再增加 1。
对于字符 'b'，它对应的索引是 1，所以 magazineCount[1] 增加 1。

magazineCount 数组更新为：
magazineCount = [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

步骤 3：遍历 ransomNote 并检查是否能构建
接下来，我们遍历 ransomNote 字符串，检查 magazineCount 中是否有足够的字母。
ransomNote = "aa"
我们需要检查是否可以从 magazineCount 中提取出两个 'a' 字符。

第一轮（检查 ransomNote[0] = 'a'）：
index = 'a' - 'a' = 0，即 index = 0。
检查 magazineCount[0]，当前值是 2，表示 magazine 中有 2 个 'a' 字符，足够使用一个。
使用一个 'a'，将 magazineCount[0] 减 1，变为 1。

第二轮（检查 ransomNote[1] = 'a'）：
index = 'a' - 'a' = 0，即 index = 0。
检查 magazineCount[0]，当前值是 1，表示 magazine 中还有 1 个 'a' 字符，足够使用一个。
使用一个 'a'，将 magazineCount[0] 减 1，变为 0。

步骤 4：返回结果
遍历完 ransomNote 中的所有字符后，我们已经从 magazine 中成功提取出所有需要的字符。因此，返回 true。
最终的 magazineCount 数组是：


magazineCount = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
这表示 magazine 中的 'a' 字符已经被完全使用，而 'b' 字符剩余 1 个，其他字符没有使用。
*/